package hot;

import javax.swing.tree.TreeNode;

public class wusisan {
//    https://leetcode.cn/problems/diameter-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        static int diameter = 0;

        public static int diameterOfBinaryTree(TreeNode root) {
            dfs(root);
            return diameter;
        }

        public static int dfs(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftLength = dfs(root.left);
            int rightLength = dfs(root.right);
//            return Math.max(diameter, leftLength + rightLength);
            diameter=Math.max(diameter,leftLength+rightLength);
            return Math.max(leftLength,rightLength)+1;
        }

        public static void main(String[] args) {
            TreeNode treeNode1 = new TreeNode(1);
            TreeNode treeNode2 = new TreeNode(2);
            TreeNode treeNode3 = new TreeNode(3);
            TreeNode treeNode4 = new TreeNode(4);
            TreeNode treeNode5 = new TreeNode(5);
            treeNode1.left = treeNode2;
            treeNode1.right = treeNode3;
            treeNode2.left = treeNode4;
            treeNode2.right = treeNode5;
            int i = diameterOfBinaryTree(treeNode1);
            System.out.println(i);

        }

    }
}
